Invert binary tree [BFS, Stack, DFS]

Time: O(N); Space: O(W); medium

Note:

• W is the max number of the nodes of the levels.

Example 1:

Input: root = {TreeNode} [4,2,7,1,3,6,9]

     4
   /   \
  2     7
 / \   / \
1   3 6   9

Output: {TreeNode} [4,7,2,9,6,3,1]

     4
   /   \
  7     2
 / \   / \
9   6 3   1

class TreeNode(object):
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None

Auxiliary Tools

from graphviz import Graph

class TreeTasks(object):
    def create_binary_tree(self, nums):
        root = None
        len_nums = len(nums)
        idx = 0
        res = self.insertLevelOrder(nums, root, idx, len_nums)
        return res

    def insertLevelOrder(self, nums, root, idx, len_nums):
        # Base case for recursion
        if idx < len_nums:
            temp = TreeNode(nums[idx])
            root = temp
            # insert left child
            root.left = self.insertLevelOrder(nums, root.left, 2 * idx + 1, len_nums)
            # insert right child
            root.right = self.insertLevelOrder(nums, root.right, 2 * idx + 2, len_nums)
        return root

    def visualize_tree(self, tree):
        def add_nodes_edges(tree, dot=None):
            # Create Graph (not Digraph) object
            if dot is None:
                dot = Graph()
                dot.node(name=str(tree), label=str(tree.val))
            # Add nodes
            if tree.left:
                dot.node(name=str(tree.left), label="."+str(tree.left.val))
                dot.edge(str(tree), str(tree.left))
                dot = add_nodes_edges(tree.left, dot=dot)
            if tree.right:
                dot.node(name=str(tree.right), label=str(tree.right.val)+".")
                dot.edge(str(tree), str(tree.right))
                dot = add_nodes_edges(tree.right, dot=dot)
            return dot
        # Add nodes recursively and create a list of edges
        dot = add_nodes_edges(tree)
        # Visualize the graph
        display(dot)
        return dot

1. BFS solution

import collections

class Queue(object):
    def __init__(self):
        self.data = collections.deque()

    def push(self, x):
        self.data.append(x)

    def peek(self):
        return self.data[0]

    def pop(self):
        return self.data.popleft()

    def size(self):
        return len(self.data)

    def empty(self):
        return len(self.data) == 0

class Solution1(object):
    """
    Time: O(N)
    Space: O(W)
    """
    def invertTree(self, root):
        '''
        :type root: TreeNode
        :rtype: TreeNode
        '''
        if root is not None:
            nodes = Queue()
            nodes.push(root)
            while not nodes.empty():
                node = nodes.pop()
                node.left, node.right = node.right, node.left
                if node.left is not None:
                    nodes.push(node.left)
                if node.right is not None:
                    nodes.push(node.right)

        return root

s = Solution1()

# root = TreeNode(4)
# root.left, root.right = TreeNode(2), TreeNode(7)
# root.left.left, root.left.right = TreeNode(1), TreeNode(3)
# root.right.left, root.right.right = TreeNode(6), TreeNode(9)

root = [4,2,7,1,3,6,9]
t = TreeTasks()
tree = t.create_binary_tree(root)
s.invertTree(tree)
assert tree.val == 4
assert tree.left.val == 7
assert tree.right.val == 2
assert tree.left.left.val == 9
assert tree.left.right.val == 6
assert tree.right.left.val == 3
assert tree.right.right.val == 1
dot = t.visualize_tree(tree)

2. Stack solution

class Solution2(object):
    '''
    Time: O(N)
    Space: O(W)
    '''
    def invertTree(self, root):
        '''
        :type root: TreeNode
        :rtype: TreeNode
        '''
        if root is not None:
            nodes = []
            nodes.append(root)
            while nodes:
                node = nodes.pop()
                node.left, node.right = node.right, node.left
                if node.left is not None:
                    nodes.append(node.left)
                if node.right is not None:
                    nodes.append(node.right)

        return root

s = Solution2()

root = [4,2,7,1,3,6,9]
t = TreeTasks()
tree = t.create_binary_tree(root)
s.invertTree(tree)
assert tree.val == 4
assert tree.left.val == 7
assert tree.right.val == 2
assert tree.left.left.val == 9
assert tree.left.right.val == 6
assert tree.right.left.val == 3
assert tree.right.right.val == 1
dot = t.visualize_tree(tree)

3. DFS, Recursive solution

class Solution3(object):
    '''
    Time: O(N)
    Space: O(W)
    '''
    def invertTree(self, root):
        '''
        :type root: TreeNode
        :rtype: TreeNode
        '''
        if root is not None:
            root.left, root.right = self.invertTree(root.right), \
                                    self.invertTree(root.left)

        return root

s = Solution3()

root = [4,2,7,1,3,6,9]
t = TreeTasks()
tree = t.create_binary_tree(root)
s.invertTree(tree)
assert tree.val == 4
assert tree.left.val == 7
assert tree.right.val == 2
assert tree.left.left.val == 9
assert tree.left.right.val == 6
assert tree.right.left.val == 3
assert tree.right.right.val == 1
dot = t.visualize_tree(tree)

See also:

https://leetcode.com/problems/invert-binary-tree

https://www.lintcode.com/problem/invert-binary-tree